public class Search2DMatrix {

	public boolean searchMatrix(int[][] matrix, int target) {
		int n = matrix.length;
		if (n == 0)
			return false;
		int m = matrix[0].length;
		if (m == 0)
			return false;
		int l = 0, r = m * n - 1, mid;
		int x, y;
		while (l <= r) {
			mid = l + r >> 1;
			x = mid / m;
			y = mid % m;
			if (matrix[x][y] > target) {
				r = mid - 1;
			} else if (matrix[x][y] < target) {
				l = mid + 1;
			} else {
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {

	}

}
